02｜差分数组（Difference Array）（知识笔记）

对应课程：lessons/02-prefix-diff-two-pointers/01-difference-array.md

识别信号

• 有很多次区间更新（加/减/赋值变形），最后一次性输出
• 朴素对每次更新遍历区间会超时

一维差分（区间加）

• 定义：diff[i] = a[i] - a[i-1]，约定 a[0]=0
• 对 [l,r] 加 x：
  • diff[l] += x
  • diff[r+1] -= x（若 r+1 在范围内）
• 还原：a[i] = a[i-1] + diff[i]（对 diff 做前缀和）

二维差分（矩形加）

对 [x1..x2][y1..y2] 加 x：

• d[x1][y1] += x
• d[x1][y2+1] -= x
• d[x2+1][y1] -= x
• d[x2+1][y2+1] += x 最后对 d 做二维前缀和还原。

常见坑

• 越界：数组通常开到 n+2 或 m+2
• 多测忘记清空 diff
• 类型溢出：叠加次数多时用 long long

自检

• [ ] 做完更新后是否还原了？
• [ ] l=1 / r=n 的边界是否正确？

个人坑位

• （例）我经常忘记处理 r+1 越界